First steps in `GAP`

GAP is a discrete algebraic computing environment (GAP stands for Groups, Algorithms, and Programming). It has a core implemented in c and has separate libraries written in its own programming language.

This language is procedural, so people who have programmed in pascal, c, maple, … have no problems in adapting. On the official GAP website you can find a lot of information concerning installation on different platforms, tutorials, manuals, and packages.

GAP packages go through a refereeing process similar to that of scientific journals. They are first deposited (and publicly accessible on the official website) and if accepted they become part of the distribution.

GAP has been maintained throughout its history by several universities, and is supported by contributions from users in the form of packages for more specific purposes.

Command line

GAP is an interpreted language (although it has a compiler). Operations can be performed directly on the command line, or scripted files written in a text editor can be read.

GAP is normally invoked using the gap command, although depending on the operating system there may be different alternatives. Once the interpreter is started, a command line appears that looks like this.

gap>

To edit the entries you want to evaluate, you can use the arrow keys together with the start and end keys. There is also the possibility of using key combinations similar to those used in a unix shell (ctr-[b,f,p,n,a,e]). The tab key is used to complete commands from the text you have entered at that moment. Thus typing Gcd+TAB results in:

gap> Gcd
    Gcd
    GcdCoeffs
    GcdInt
    GcdOp
    GcdRepresentation
    GcdRepresentationOp
    Gcdex

To exit the command line, you can use the command quit;, or press ctr-d.

The end of a line is not indicated by a carriage return, but by ; (to evaluate, press enter). This allows you to write multi-line statements.

gap> 1+
> 2;
3

On jupyter to evaluate you have to press shift+enter.

1+
2+3;

The working session can be stored in a file for later editing using the LogTo command. With LogTo("tests/log"); we save to the log file in the tests folder. With LogTo(); we interrupt the recording.

We can read a script with the Read command (in this example one.g contains only a:=1;).

Read("pruebas/uno.g");

a;

Note that the slashes are in the form /, even on windows.

Help is accessed using a question mark. For example, ?LogTo shows help for that command.

The operations of addition and product depend on the arguments that accompany them. They can represent the sum of integers, or of matrices, or of vector subspaces… The product can even mean the composition of two permutations, and the power (^) the image of a point by a permutation.

[1,2,3]+[1,2,7,8];

[ 2, 4, 10, 8 ]

(1,2)*(2,5);

(1,5,2)

1^(1,2,3);

The symbols =, <, >, <=, >=, and <> are used to denote equality, less than, greater than, less than or equal, greater than or equal, and different, respectively sirven para denotar igualdad, ser mayor, menor, menor o igual, mayor o igual y distinto, respectivamente.

2=1+1;

true

[1,2]<[3];

true

[1,2]>[1,3];

false

1<>1;

false

Identifiers

If we are going to use an object several times, we can assign it a name for convenience.

a:=2^10;

If we want to inhibit the output, we write an extra semicolon at the end of the assignment.

b:=a;;

We can visualise the variables defined so far as follows.

NamesUserGVars();

[ "AcceptNewConnection", "AttachServingSocket", "BGJobByForkType", "BackgroundJobByFork", "BackgroundJobByForkChild", "BackgroundJobByForkOptions", "BackgroundJobsFamily", "CRYPTING_HexStringIntPad", "CRYPTING_HexStringIntPad8", "CRYPTING_SHA256_FINAL", "CRYPTING_SHA256_HMAC", "CRYPTING_SHA256_INIT", "CRYPTING_SHA256_State_Family", "CRYPTING_SHA256_State_Type", "CRYPTING_SHA256_UPDATE", "ChangeDirectoryCurrent", "CheckForUpdates", "CloseConnection", "CloseHTTPConnection", "CompareTimes", "DifferenceTimes", "DoIO", "DoQueues", "FileFamily", "FileType", "FixChunkedBody", "GAPJupyterKernelType", "GET_HELP_URL", "GapToJsonStream", "GapToJsonString", "GetInput", "GetLenFrom8Bytes", "HMACSHA256", "HPCGAPJupyterKernelType", "HTTPRequest", "HTTPTimeoutForSelect", "HasJupyterRenderableData", "HasJupyterRenderableMetadata", "HasProcessID", "HasTerminated", "HexStringUUID", "IO", "IOHub", "IOHubFamily", "IOHubType", "IO_AddToPickled", "IO_AddToUnpickled", "IO_ClearPickleCache", "IO_Close", "IO_CloseAllFDs", "IO_CompressedFile", "IO_EOF", "IO_Environment", "IO_Error", "IO_File", "IO_FileFilterString", "IO_FilteredFile", "IO_FinalizePickled", "IO_FinalizeUnpickled", "IO_FindExecutable", "IO_Flush", "IO_FlushNonBlocking", "IO_ForkExecWithFDs", "IO_GenericObjectPickler", "IO_GenericObjectUnpickler", "IO_GetFD", "IO_GetWBuf", "IO_HasData", "IO_IgnorePid", "IO_InstallSIGCHLDHandler", "IO_IsAlreadyPickled", "IO_ListDir", "IO_MakeEnvList", "IO_MakeIPAddressPort", "IO_Nothing", "IO_OK", "IO_PICKLECACHE", "IO_PackageIsLoaded", "IO_Pickle", "IO_PickleByString", "IO_PipeThrough", "IO_PipeThroughWithError", "IO_Popen", "IO_Popen2", "IO_Popen3", "IO_Read", "IO_ReadAttribute", "IO_ReadBlock", "IO_ReadLine", "IO_ReadLines", "IO_ReadSmallInt", "IO_ReadUntilEOF", "IO_ReadyForFlush", "IO_ReadyForWrite", "IO_RestoreSIGCHLDHandler", "IO_Result", "IO_ResultsFamily", "IO_Select", "IO_SendStringBackground", "IO_StartPipeline", "IO_StringFilterFile", "IO_Unpickle", "IO_UnpickleByEvalString", "IO_UnpickleByFunction", "IO_Unpicklers", "IO_WaitPid", "IO_WrapFD", "IO_Write", "IO_WriteAttribute", "IO_WriteFlush", "IO_WriteLine", "IO_WriteLines", "IO_WriteNonBlocking", "IO_WriteSmallInt", "IO_accept", "IO_bind", "IO_chdir", "IO_chmod", "IO_chown", "IO_close", "IO_closedir", "IO_connect", "IO_creat", "IO_dup", "IO_dup2", "IO_environ", "IO_execv", "IO_execve", "IO_execvp", "IO_exit", "IO_fchmod", "IO_fchown", "IO_fcntl", "IO_fork", "IO_fstat", "IO_getcwd", "IO_gethostbyname", "IO_gethostname", "IO_getpid", "IO_getppid", "IO_getsockname", "IO_getsockopt", "IO_gettimeofday", "IO_gmtime", "IO_kill", "IO_lchown", "IO_link", "IO_listen", "IO_localtime", "IO_lseek", "IO_lstat", "IO_make_sockaddr_in", "IO_mkdir", "IO_mkdtemp", "IO_mkfifo", "IO_mknod", "IO_mkstemp", "IO_open", "IO_opendir", "IO_pipe", "IO_read", "IO_readdir", "IO_readlink", "IO_recv", "IO_recvfrom", "IO_rename", "IO_rewinddir", "IO_rmdir", "IO_seekdir", "IO_select", "IO_send", "IO_sendto", "IO_setsockopt", "IO_socket", "IO_stat", "IO_symlink", "IO_telldir", "IO_unlink", "IO_write", "ISO8601Stamp", "InfoIO", "InputQueue", "IsBackgroundJob", "IsBackgroundJobByFork", "IsFile", "IsGAPJupyterKernel", "IsHPCGAPJupyterKernel", "IsIOHub", "IsIOHubCat", "IsIdle", "IsJupyterKernel", "IsJupyterRenderable", "IsJupyterRenderableRep", "IsOutputStreamZmqRep", "IsRealRandomSource", "IsSHA256State", "IsUUID", "IsUUIDBlistRep", "IsWorkerFarm", "IsWorkerFarmByFork", "IsZmqSocket", "JSON_ESCAPE_STRING", "JSON_STREAM_TO_GAP", "JSON_STRING_TO_GAP", "JUPYTER_Complete", "JUPYTER_FindHelp", "JUPYTER_FindManSection", "JUPYTER_FormatKnown", "JUPYTER_HELP", "JUPYTER_HELP_SHOW_MATCHES", "JUPYTER_Inspect", "JUPYTER_KERNEL_MODE_CONTROL", "JUPYTER_KERNEL_MODE_EXEC", "JUPYTER_KernelLoop", "JUPYTER_KernelStart_GAP", "JUPYTER_KernelStart_HPC", "JUPYTER_LogProtocol", "JUPYTER_UnlogProtocol", "JUPYTER_print", "JsonStreamToGap", "JsonStringToGap", "JupyterDefaultKernelConfig", "JupyterMsg", "JupyterMsgDecode", "JupyterMsgEncode", "JupyterMsgRecv", "JupyterMsgSend", "JupyterRender", "JupyterRenderable", "JupyterRenderableData", "JupyterRenderableMetadata", "JupyterRenderableType", "JupyterSplashDot", "JupyterSplashSubgroupLattice", "JupyterSplashTikZ", "Kill", "LastReadValue", "NewConnection", "NewJupyterKernel", "NewTCPConnection", "NewUUID", "OpenHTTPConnection", "OutputQueue", "OutputStreamZmq", "OutputStreamZmqType", "ParDoByFork", "ParDoByForkOptions", "ParListByFork", "ParListByForkOptions", "ParListWorker", "ParMapReduceByFork", "ParMapReduceByForkOptions", "ParMapReduceWorker", "ParTakeFirstResultByFork", "ParTakeFirstResultByForkOptions", "ParWorkerFarmByFork", "ParWorkerFarmByForkOptions", "Pickup", "ProcessID", "RandomUUID", "ReadWeb", "Run", "SHA256String", "SetJupyterRenderableData", "SetJupyterRenderableMetadata", "SetProcessID", "Shutdown", "ShutdownServingSocket", "SingleHTTPRequest", "StoreLenIn8Bytes", "StringUUID", "Submit", "SubmitOutput", "SynchronizationFamily", "TYPE_ZMQ_SOCKET", "UUIDFamily", "UUIDType", "WaitUntilIdle", "WorkerFarmByForkType", "WorkerFarmsFamily", "ZmqAttach", "ZmqAttachedSocket", "ZmqBind", "ZmqClose", "ZmqConnect", "ZmqDealerSocket", "ZmqGetIdentity", "ZmqGetReceiveBufferSize", "ZmqGetReceiveCapacity", "ZmqGetSendBufferSize", "ZmqGetSendCapacity", "ZmqHasMore", "ZmqIsBound", "ZmqIsConnected", "ZmqIsOpen", "ZmqPoll", "ZmqPublisherSocket", "ZmqPullSocket", "ZmqPushSocket", "ZmqReceive", "ZmqReceiveList", "ZmqReceiveListAsString", "ZmqReplySocket", "ZmqRequestSocket", "ZmqRouterSocket", "ZmqSend", "ZmqSetIdentity", "ZmqSetReceiveBufferSize", "ZmqSetReceiveCapacity", "ZmqSetSendBufferSize", "ZmqSetSendCapacity", "ZmqSocket", "ZmqSocketType", "ZmqSocketURI", "ZmqSubscribe", "ZmqSubscriberSocket", "ZmqUnsubscribe", "_BUFFER", "_GapToJsonStreamInternal", "_JSON_Globals", "_JSON_addRef", "_JSON_clearRefs", "_KERNEL", "a", "b" ]

Variables in gap have no type, the characteristics of the object they refer to are stored in the object itself. In fact, we can reuse the same variable to denote different types of data.

a:=1;

a:=(1,2);

(1,2)

a:=[1,2];

[ 1, 2 ]

The last identifier is used to refer to the last output (last2 and last3 are also available).

In gap there is a convention of writing global variables and variables used in libraries starting with capital letters.

Functions are also objects, and can be defined in various ways. We can use a classical procedure.

f:=function(x)
    return x^2;
end;

function( x ) ... end

f(3);

And we can also use \(\lambda\)-calculus-style notation.

g:=x->x^2;
g(3);

function( x ) ... end

Lists

Lists in gap are written, as we have already seen in some examples above, as a sequence of elements delimited by square brackets. Such sequences need not be homogeneous. When working with lists we have to pay attention to some functions that are ‘destructive’, that is, they modify some of the arguments passed to them. This is partly because when you assign an identifier to a list, you do not assign it to the object as such, but to its position in memory.

a:=[1,"a"];

[ 1, "a" ]

b:=a;

[ 1, "a" ]

b[2]:=3;

a;

[ 1, 3 ]

As we have seen in this example list[n] accesses the nth element of the list (starting at 1; in other languages the first position is the one corresponding to index 0).

We can use the ShallowCopy command to make a copy of a list, creating a new object.

a:=[1,"a"];

[ 1, "a" ]

b:=ShallowCopy(a);

[ 1, "a" ]

b[2]:=3;

b;

[ 1, 3 ]

a;

[ 1, "a" ]

There are many ways to define and modify lists, some examples are given below.

a:=[1,"a"];

[ 1, "a" ]

To append to a the elements of another list, we can use Append:

Append(a,[2,3]);

a;

[ 1, "a", 2, 3 ]

If we want to add an element at the end of our list, we use Add.

Add(a,5);

a;

[ 1, "a", 2, 3, 5 ]

Concatenation returns a new list from two given lists, concatenating them without modifying them.

Concatenation(a,[8,9]);

[ 1, "a", 2, 3, 5, 8, 9 ]

a;

[ 1, "a", 2, 3, 5 ]

Filtered` can be used to filter the elements of a list that meet a given condition.

l:=Filtered([1..100],IsPrime);

[ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97 ]

We can also apply a function to all the elements of a list.

List(l,x->x^2);

[ 4, 9, 25, 49, 121, 169, 289, 361, 529, 841, 961, 1369, 1681, 1849, 2209, 2809, 3481, 3721, 4489, 5041, 5329, 6241, 6889, 7921, 9409 ]

Sometimes it is convenient to use sets instead of lists, as their elements are sorted (if they are comparable to each other) and the membership of an element is quicker to resolve.

a:=[1,2,1,2];

[ 1, 2, 1, 2 ]

Set(a);

[ 1, 2 ]

a;

[ 1, 2, 1, 2 ]

3 in a;

false

There are certain commands whose output is a set.

a:=[1,2];

[ 1, 2 ]

b:=[2,3];

[ 2, 3 ]

u:=Union(a,b);

[ 1, 2, 3 ]

IsSet(u);

true

Intersection(a,b);

[ 2 ]

Ranges

The use of .. can be used in a variety of ways, and captures the idea of range.

l:=[1..20];

[ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20 ]

l{[3,5..9]};

[ 3, 5, 7, 9 ]

lc:=List(l,x->x^2);

[ 1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225, 256, 289, 324, 361, 400 ]

lc{[20,19..10]};

[ 400, 361, 324, 289, 256, 225, 196, 169, 144, 121, 100 ]

Registers

In gap we can create records with custom fields using rec.

r:=rec(a:=1,b:="2");

rec( a := 1, b := "2" )

We can add new fields, or modify existing ones, simply by assigning them a value.

r.c:=rec(d:=1,e:=3);

rec( d := 1, e := 3 )

r;

rec( a := 1, b := "2", c := rec( d := 1, e := 3 ) )

r.a:=5;

r;

rec( a := 5, b := "2", c := rec( d := 1, e := 3 ) )

To access a field value, we use ..

r.c.d;

We can see the fields defined with RecNames.

RecNames(r);

[ "b", "a", "c" ]

Or see whether a field is assigned or not

IsBound(r.g);

false

Unbind(r.b);

r;

rec( a := 5, c := rec( d := 1, e := 3 ) )

As with lists, if you want to make a copy, it is advisable to use ShallowCopy.

rr:=ShallowCopy(r);

rec( a := 5, c := rec( d := 1, e := 3 ) )

rr.c.d:=4;

r;

rec( a := 5, c := rec( d := 4, e := 3 ) )

The problem here is that r itself contains another record. To avoid this, we use StructuralCopy.

rr:=StructuralCopy(r);

rec( a := 5, c := rec( d := 4, e := 3 ) )

rr.c.d:=1;

r;

rec( a := 5, c := rec( d := 4, e := 3 ) )

rr;

rec( a := 5, c := rec( d := 1, e := 3 ) )

Some programming examples

In gap you can use commands like for, while, repeat … until to make loops.

Let us see how to define the factorial in different ways, using different implementation styles.

f:=function(x)
    local p, i; #variable local para el producto parcial y contador
    
    p:=1;
    for i in [1..x] do
        p:=p*i;
    od; #final de bucle
    
    return p; #salida
end;

function( x ) ... end

f(3);

Recursively…

f:=function(x)

    if x=0 then
        return 1;
    fi;
    
    return x*f(x-1);
end;

function( x ) ... end

f(100);

93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

Using list-specific functions and \(\lambda\)-expressions …

f:=x->Product([1..x]);

function( x ) ... end

f(150);

57133839564458545904789328652610540031895535786011264182548375833179829124845398393126574488675311145377107878746854204162666250198684504466355949195922066574942592095735778929325357290444962472405416790722118445437122269675520000000000000000000000000000000000000

We now calculate the first perfect integer, and the perfect integers between 1 and 100000. For this we will use First.

es_perfecto:=x->(Sum(DivisorsInt(x))=2*x);

function( x ) ... end

First([1..200],es_perfecto);

Filtered([1..1000],es_perfecto);

[ 6, 28, 496 ]

Let us see if all the numbers between 100 and 500 are perfect, or if there are any.

ForAll([100..500], es_perfecto);

false

ForAny([100..500], es_perfecto);

true

We do something similar with pairs of friendly numbers.

son_amigos:=function(x,y)
    local dx, dy; #divisores de x e y
    
    if x=y or IsPrime(x) then 
        return false;
    fi; #queremos buscar parejas distintas y que no sean primos
    dx:=List(DivisorsInt(x)); 
    Remove(dx);; #le quitamos x
    dy:=List(DivisorsInt(y));
    Remove(dy);; #le quitamos y
    return (Sum(dx)=y) and (x=Sum(dy));
end;

function( x, y ) ... end

To see which numbers between 1 and 50 have friends, we write, for example, the following.

l:=Filtered([1..250],x->ForAny([1..500],y->son_amigos(x,y)));

[ 220 ]

List(l,x->[x,First([1..550],y->son_amigos(x,y))]);

[ [ 220, 284 ] ]

If we want to search in a larger list, we can use iterators.

l:=IteratorOfCartesianProduct([1..1500],[1..1500]);

<object>

for x in l do
if (x[1]<x[2]) and son_amigos(x[1],x[2]) then
    Print(x,"\n");
fi;
od;

[ 220, 284 ]
[ 1184, 1210 ]